package dataStructure.study.sort;

/**
 * Author: shangsf
 * Date: 2021/4/10 16:50
 * Description:归并排序，时间复杂度O(nlogn)
 * 1.先二分法把数组分成两部分，递归到每部分只有1个元素为止
 * 2.然后再逐步合并并排序两部分的的数据，直到合并到1个为止
 */
public class MergeSort {
    public static void sort(int[] array) {
        if (array == null || array.length == 1) {
            return;
        }
        int n = array.length;

        mergeSort(array,0,n-1);
    }

    static void mergeSort(int[] array,int begin,int end){
        if(begin>=end){
            return;
        }
        int mid=(begin+end)/2;
        mergeSort(array,begin,mid);
        mergeSort(array,mid+1,end);
        mergeSort(array,begin,mid,mid+1,end);
    }

    static void mergeSort(int[] array,int begin1,int end1,int begin2,int end2){
        int i=begin1,j=begin2;
        int[] tmp=new int[end2-begin1+1];
        int x=-1;
        while (i<=end1&&j<=end2){
            x++;
            if(array[i]<array[j]){
                tmp[x]=array[i];
                i++;
            }else {
                tmp[x]=array[j];
                j++;
            }
        }
        if(i>end1){
            for(;j<=end2;j++){
                x++;
                tmp[x]=array[j];
            }
        }else {
            for(;i<=end1;i++){
                x++;
                tmp[x]=array[i];
            }
        }
        i=begin1;x=0;
        for(;i<=end2;i++,x++){
            array[i]=tmp[x];
        }
    }
}
